{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimize Maximum of Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #binary-search #dynamic-programming #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #二分查找 #动态规划 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimizeArrayValue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小化数组中的最大值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的数组&nbsp;<code>nums</code>&nbsp;，它含有&nbsp;<code>n</code>&nbsp;个非负整数。</p>\n",
    "\n",
    "<p>每一步操作中，你需要：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选择一个满足&nbsp;<code>1 &lt;= i &lt; n</code>&nbsp;的整数 <code>i</code>&nbsp;，且&nbsp;<code>nums[i] &gt; 0</code>&nbsp;。</li>\n",
    "\t<li>将&nbsp;<code>nums[i]</code>&nbsp;减 1 。</li>\n",
    "\t<li>将&nbsp;<code>nums[i - 1]</code>&nbsp;加 1 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>你可以对数组执行 <strong>任意</strong>&nbsp;次上述操作，请你返回可以得到的 <code>nums</code>&nbsp;数组中<b>&nbsp;最大值</b>&nbsp;<strong>最小</strong> 为多少。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [3,7,1,6]\n",
    "<b>输出：</b>5\n",
    "<strong>解释：</strong>\n",
    "一串最优操作是：\n",
    "1. 选择 i = 1 ，nums 变为 [4,6,1,6] 。\n",
    "2. 选择 i = 3 ，nums 变为 [4,6,2,5] 。\n",
    "3. 选择 i = 1 ，nums 变为 [5,5,2,5] 。\n",
    "nums 中最大值为 5 。无法得到比 5 更小的最大值。\n",
    "所以我们返回 5 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [10,1]\n",
    "<b>输出：</b>10\n",
    "<strong>解释：</strong>\n",
    "最优解是不改动 nums ，10 是最大值，所以返回 10 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimize-maximum-of-array](https://leetcode.cn/problems/minimize-maximum-of-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimize-maximum-of-array](https://leetcode.cn/problems/minimize-maximum-of-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,7,1,6]', '[10,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        max_val = 0\n",
    "        n = len(nums)\n",
    "        su = 0\n",
    "        for i in range(n):\n",
    "            su += nums[i]\n",
    "            max_val = max(max_val, (su - 1) // (i + 1) + 1)\n",
    "        return max_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        def check(mx: int) -> bool:\n",
    "            # if mx < nums[0]:\n",
    "            #     return False\n",
    "            buf = nums.copy()\n",
    "            for i in range(len(buf) - 1, 0, -1):\n",
    "                dif = buf[i] - mx\n",
    "                if dif > 0:\n",
    "                    buf[i - 1] += dif\n",
    "                # print(buf[i - 1])\n",
    "            # print(mx, buf[0])\n",
    "            return buf[0] <= mx\n",
    "\n",
    "        l, r = nums[0], max(nums)\n",
    "        while l <= r:\n",
    "            m = l + (r - l) // 2\n",
    "            if check(m):\n",
    "                r = m - 1\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        k=max(nums)\n",
    "        if nums[0]==k:\n",
    "            return k\n",
    "        dp=[0]*(len(nums))\n",
    "        dp[0]=nums[0]\n",
    "        sum1=nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            sum1+=nums[i]\n",
    "            if nums[i]<=dp[i-1]:\n",
    "                dp[i]=dp[i-1]\n",
    "            else:\n",
    "                if sum1%(i+1)==0:\n",
    "                    dp[i]=sum1//(i+1)\n",
    "                else:\n",
    "                    dp[i]=1+sum1//(i+1)\n",
    "                    if dp[i]<dp[i-1]:\n",
    "                        dp[i]=dp[i-1]\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        def canBeAccommodated(k: int) -> bool:\n",
    "            accommodation = 0\n",
    "            for num in nums:\n",
    "                if num < k:\n",
    "                    accommodation += k - num\n",
    "                else:\n",
    "                    accommodation -= num - k\n",
    "                if accommodation < 0:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        left, right = min(nums), max(nums)\n",
    "\n",
    "        while left <= right:\n",
    "            middle = math.floor((left + right) / 2)\n",
    "            if canBeAccommodated(middle):\n",
    "                right = middle - 1\n",
    "            else:\n",
    "                left = middle + 1\n",
    "\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        def check(limit: int) -> bool:\n",
    "            extra = 0\n",
    "            for i in range(len(nums) - 1, 0, -1):\n",
    "                extra = max(nums[i] + extra - limit, 0)\n",
    "            return nums[0] + extra <= limit\n",
    "        return bisect_left(range(max(nums)), True, key=check)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        s = 0\n",
    "        ans = nums[0]\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            s += nums[i]\n",
    "            ans = max(ans, ceil(s / (i + 1)))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        def check(t, n):\n",
    "            nn = nums[:]\n",
    "            for i in range(n-1, 0, -1):\n",
    "                if nn[i] > t :\n",
    "                    nn[i-1] = nn[i-1] + nn[i] - t\n",
    "                    nn[i] = t\n",
    "            for i in range(n):\n",
    "                if nn[i] > t:\n",
    "                    return False\n",
    "            return True\n",
    "        # print(check(4, len(nums)))\n",
    "        mn, mx = min(nums), max(nums)\n",
    "        n = len(nums)\n",
    "        while mn <= mx:\n",
    "            mid = (mn + mx) >> 1\n",
    "\n",
    "            if check(mid, n):\n",
    "                mx = mid - 1\n",
    "            else:\n",
    "                mn = mid + 1\n",
    "        return mn\n",
    "\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        Max = 0\n",
    "        Max_i = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if x > Max:\n",
    "                Max = x\n",
    "                Max_i = i\n",
    "        if Max_i == 0:\n",
    "            return nums[0]\n",
    "        def check(limit: int) -> int:\n",
    "            a = nums.copy()\n",
    "            for i in range(len(a) - 1, 0, -1):\n",
    "                x = a[i]\n",
    "                if x > limit:\n",
    "                    a[i - 1] += x - limit\n",
    "            return a[0] <= limit\n",
    "        return bisect_left(range(Max), True, key=check)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        Max = 0\n",
    "        Max_i = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if x > Max:\n",
    "                Max = x\n",
    "                Max_i = i\n",
    "        if Max_i == 0:\n",
    "            return nums[0]\n",
    "        def check(limit: int) -> int:\n",
    "            a = nums.copy()\n",
    "            for i in range(len(a) - 1, 0, -1):\n",
    "                x = a[i]\n",
    "                if x > limit:\n",
    "                    a[i - 1] += x - limit\n",
    "            return a[0] <= limit\n",
    "        return bisect_left(range(Max), True, key=check)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        \"\"\" Greedy + Binary Search \"\"\" \n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        def check(limit, nums):\n",
    "            for i in range(n-1, 0, -1):\n",
    "                if nums[i] > limit:\n",
    "                    temp = nums[i] - limit \n",
    "                    nums[i] -= temp\n",
    "                    nums[i-1] += temp\n",
    "            return nums[0] > limit \n",
    "\n",
    "        # binary search find mininum \n",
    "        left, right = 0, max(nums) + 1 \n",
    "        while left < right:\n",
    "            mid = (right - left) // 2 + left \n",
    "            c_nums = nums.copy()\n",
    "            if check(mid, c_nums):\n",
    "                left = mid + 1 \n",
    "            else:\n",
    "                right = mid \n",
    "\n",
    "        return left "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        def check(mx: int) -> bool:\n",
    "            # if mx < nums[0]:\n",
    "            #     return False\n",
    "            buf = nums.copy()\n",
    "            for i in range(len(buf) - 1, 0, -1):\n",
    "                dif = buf[i] - mx\n",
    "                if dif > 0:\n",
    "                    buf[i - 1] += dif\n",
    "            return buf[0] <= mx\n",
    "\n",
    "        l, r = nums[0], max(nums)\n",
    "        while l <= r:\n",
    "            m = l + (r - l) // 2\n",
    "            if check(m):\n",
    "                r = m - 1\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        left, right = min(nums), max(nums)\n",
    "        while left < right:\n",
    "            mid = left + right >> 1\n",
    "            if self.check(mid, nums[:]):\n",
    "                right   = mid\n",
    "            else:\n",
    "                left    = mid + 1\n",
    "        return left\n",
    "    def check(self, target: int, nums: List[int]) -> bool:\n",
    "        for ii in range(len(nums)-1, 0, -1):\n",
    "            delta       = nums[ii] - target\n",
    "            nums[ii-1]  += max(delta, 0)\n",
    "        return nums[0] <= target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        left, right = min(nums), max(nums)\n",
    "        while left < right:\n",
    "            mid = left + right >> 1\n",
    "            if self.check(mid, nums[:]):\n",
    "                right   = mid\n",
    "            else:\n",
    "                left    = mid + 1\n",
    "        return left\n",
    "    def check(self, target: int, nums: List[int]) -> bool:\n",
    "        for ii in range(len(nums)-1, 0, -1):\n",
    "            delta       = nums[ii] - target\n",
    "            nums[ii-1]  += max(delta, 0)\n",
    "        return nums[0] <= target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        '''\n",
    "        前方的较小数可以接受后方较大数多余的数字\n",
    "        copy() 函数用于复制列表，类似于 a[:]\n",
    "        https://www.jb51.net/article/260044.htm\n",
    "        '''\n",
    "        def check(limit):\n",
    "            a = copy.deepcopy(nums)\n",
    "            for i in range(len(a)-1,0,-1):\n",
    "                x = a[i]\n",
    "                if x > limit:\n",
    "                    a[i-1] += x- limit\n",
    "            return a[0] <= limit\n",
    "        l,r = 0,max(nums)\n",
    "        while l < r:\n",
    "            mid = (l+r)//2\n",
    "            if check(mid):#最小\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n",
    "            \n",
    "            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        def check(limit: int) -> int:\n",
    "            a = nums.copy()\n",
    "            for i in range(len(a) - 1, 0, -1):\n",
    "                x = a[i]\n",
    "                if x > limit:\n",
    "                    a[i - 1] += x - limit\n",
    "            return a[0] <= limit\n",
    "        return bisect_left(range(max(nums)), True, key=check)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        def check(x):\n",
    "            arr = nums.copy()\n",
    "            for i in range(n - 1, 0, -1):\n",
    "                if arr[i] > x:\n",
    "                    arr[i - 1] += arr[i] - x\n",
    "            return arr[0] <= x\n",
    "\n",
    "        n = len(nums)\n",
    "        return bisect_right(range(max(nums) + 1), 0, key=check)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        def greedy(nums,val):\n",
    "            n = nums.copy()\n",
    "            for i in range(len(n)-1,-1,-1):\n",
    "                if n[i]>val:\n",
    "                    n[i-1]+=(n[i]-val)\n",
    "            return n[0]<=val\n",
    "\n",
    "        return bisect_right(range(10**9),0,key=lambda x:greedy(nums,x))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        '''\n",
    "        前方的较小数可以接受后方较大数多余的数字\n",
    "        '''\n",
    "        def check(limit):\n",
    "            a = nums.copy()\n",
    "            for i in range(len(a)-1,0,-1):\n",
    "                x = a[i]\n",
    "                if x > limit:\n",
    "                    a[i-1] += x- limit\n",
    "            return a[0] <= limit\n",
    "        l,r = 0,max(nums)\n",
    "        while l < r:\n",
    "            mid = (l+r)//2\n",
    "            if check(mid):#最小\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n",
    "            \n",
    "            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        '''\n",
    "        前方的较小数可以接受后方较大数多余的数字\n",
    "        copy() 函数用于复制列表，类似于 a[:]\n",
    "        https://www.jb51.net/article/260044.htm\n",
    "        切片方法进行拷贝，也仅对第一层为深拷贝\n",
    "        '''\n",
    "        def check(limit):\n",
    "            a = nums[:]\n",
    "            for i in range(len(a)-1,0,-1):\n",
    "                x = a[i]\n",
    "                if x > limit:\n",
    "                    a[i-1] += x- limit\n",
    "            return a[0] <= limit\n",
    "        l,r = 0,max(nums)\n",
    "        while l < r:\n",
    "            mid = (l+r)//2\n",
    "            if check(mid):#最小\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n",
    "            \n",
    "            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        prefix_sum = itertools.accumulate(nums)\n",
    "        # 向上取整： ceil(s / i) == (s + i - 1) // i \n",
    "        average_list = list( (s + i - 1) // i  for i, s in enumerate(prefix_sum, 1))\n",
    "        # print(average_list)\n",
    "        return max(average_list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        def check(goal:int)->bool:\n",
    "            cpy_nums=nums.copy()\n",
    "            for i in range(n-1,-1,-1):\n",
    "                if cpy_nums[i]>goal:\n",
    "                    cpy_nums[i-1]+=cpy_nums[i]-goal\n",
    "            if cpy_nums[0]<=goal:\n",
    "                return True\n",
    "            return False\n",
    "        mx=max(nums)\n",
    "        left = 0\n",
    "        right=mx\n",
    "        while left<right:\n",
    "            mid=int((left+right)/2)\n",
    "            if check(mid):\n",
    "                right=mid\n",
    "            else:\n",
    "                left=mid+1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        \"\"\" Binary Search \"\"\" \n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        def check(limit, nums):\n",
    "            for i in range(n-1, 0, -1):\n",
    "                if nums[i] > limit:\n",
    "                    temp = nums[i] - limit \n",
    "                    nums[i] -= temp\n",
    "                    nums[i-1] += temp\n",
    "            return nums[0] > limit \n",
    "\n",
    "        # binary search find mininum \n",
    "        left, right = 0, max(nums) + 1 \n",
    "        while left < right:\n",
    "            mid = (right - left) // 2 + left \n",
    "            c_nums = [i for i in nums]\n",
    "            if check(mid, c_nums):\n",
    "                left = mid + 1 \n",
    "            else:\n",
    "                right = mid \n",
    "\n",
    "        return left "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        tot = sum(nums)\n",
    "        n = len(nums)\n",
    "        if tot % n == 0:\n",
    "            cp = tot//n\n",
    "        else:\n",
    "            cp = tot//n+1\n",
    "        cpn = max(cp,nums[0])\n",
    "        k = n\n",
    "        for i in range(n-1,0,-1):\n",
    "            cp = cpn\n",
    "            if nums[i] <= cp:\n",
    "                tot -= nums[i]\n",
    "                k -= 1\n",
    "                if tot%k == 0:\n",
    "                    cp = tot//k\n",
    "                else:\n",
    "                    cp = tot//k+1\n",
    "                cp = max(cp,nums[0])\n",
    "            else:\n",
    "                nums[i-1] += nums[i]-cp\n",
    "                tot -= cp\n",
    "                k-=1\n",
    "            cpn = max(cp,cpn)\n",
    "        return cpn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        min max val is equivalent to binary search\n",
    "        \"\"\"\n",
    "        # def check(limit: int) -> bool:\n",
    "        #     extra = 0\n",
    "        #     for i in range(len(nums) - 1, 0, -1):\n",
    "        #         extra = max(nums[i] + extra - limit, 0)\n",
    "        #     return nums[0] + extra <= limit\n",
    "        # return bisect_left(range(max(nums)), True, key=check)\n",
    "        return max((s + i - 1) // i for i, s in enumerate(accumulate(nums), 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, a) -> int:\n",
    "        \n",
    "        def check(target):\n",
    "            nums = a.copy()\n",
    "            for i in range(len(nums) - 1, 0, -1):\n",
    "                if nums[i] <= target:\n",
    "                    continue\n",
    "                nums[i - 1] += nums[i] - target\n",
    "            return nums[0] <= target\n",
    "        \n",
    "        l, r = 0, max(a)\n",
    "        ans = float('inf')\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        s = sum(nums)\n",
    "        if s%n == 0:\n",
    "            base = s//n\n",
    "        else:\n",
    "            base = (s//n)+1\n",
    "        prefix = [nums[0] for i in range(n)]\n",
    "        for i in range(1, n):\n",
    "            prefix[i] = nums[i]+prefix[i-1]\n",
    "            \n",
    "        for i in range(n-1, 0, -1):\n",
    "            if nums[i] <= min(nums[i-1], base):\n",
    "                if prefix[i-1]%i == 0:\n",
    "                    base = prefix[i-1]//i\n",
    "                else:\n",
    "                    base = prefix[i-1]//i+1\n",
    "                continue\n",
    "            if nums[i] > base:\n",
    "                nums[i-1] += nums[i]-base\n",
    "                nums[i] = base\n",
    "                prefix[i-1] += nums[i]-base\n",
    "        return max(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "from queue import Queue\n",
    "from functools import lru_cache\n",
    "from typing import *\n",
    "import heapq\n",
    "import random\n",
    "from sortedcontainers import SortedList, SortedSet, sorteddict\n",
    "from typing import *\n",
    "import math\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        def check(s):\n",
    "            ds = nums[::]\n",
    "            for i in range(n-1, 0, -1):\n",
    "                if ds[i] > s:\n",
    "                    tmp = ds[i] - s\n",
    "                    ds[i-1] += tmp\n",
    "            return ds[0] <= s\n",
    "\n",
    "        l = 0\n",
    "        r = max(nums)\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "\n",
    "            if check(mid):\n",
    "                r = mid \n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        def cal(x):\n",
    "            a = [i for i in nums]\n",
    "            n = len(nums)\n",
    "            for i in range(n - 1, 0, -1):\n",
    "                if a[i] > x:\n",
    "                    a[i - 1] += a[i] - x\n",
    "            return a[0] <= x\n",
    "        l = min(nums)\n",
    "        r = max(nums)\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if cal(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        def check(max_p):\n",
    "            nonlocal n\n",
    "            p = copy.copy(nums)\n",
    "            for i in range(n-1,0,-1):\n",
    "                x = p[i]\n",
    "                if x > max_p:\n",
    "                    c = x - max_p\n",
    "                    p[i-1] += c\n",
    "            return p[0] <= max_p\n",
    "        \n",
    "        left = min(nums)\n",
    "        right = max(nums)\n",
    "        while left <= right:\n",
    "            mid = (left+right)//2\n",
    "            if check(mid):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        current_avg = mean(nums)\n",
    "        print(current_avg)\n",
    "        adjusted = [0] * len(nums)\n",
    "        prefix_sum = 0\n",
    "        for i in range(len(nums)):\n",
    "            this_num = nums[i]\n",
    "            this_prefix_sum = prefix_sum + this_num\n",
    "            prefix_sum = this_prefix_sum\n",
    "            if this_num <= current_avg:\n",
    "                adjusted[i] = this_num\n",
    "                continue\n",
    "            this_avg = ceil(this_prefix_sum / (i+1))\n",
    "            adjusted[i] = this_avg\n",
    "        print(adjusted)\n",
    "        return max(adjusted)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        def check(limit):\n",
    "            ns = nums[:]\n",
    "            for i in range(n-1, 0, -1):\n",
    "                ns[i-1] += max(ns[i] - limit, 0)\n",
    "            return ns[0] <= limit\n",
    "        \n",
    "        return bisect_left(range(max(nums)), True, key=check)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 最大值最小化\n",
    "# \n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        \n",
    "        def check(max_num):\n",
    "            temp = nums.copy()\n",
    "            for i in range(n-1, 0, -1):\n",
    "                if temp[i]>max_num:\n",
    "                    temp[i-1] += temp[i]-max_num\n",
    "            return temp[0]<=max_num\n",
    "\n",
    "        left, right = 0, max(nums)\n",
    "        while left <= right:\n",
    "            mid = (left+right)//2\n",
    "            if check(mid): right = mid-1\n",
    "            else: left = mid+1\n",
    "        return left\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        def check(bar):\n",
    "            a = nums.copy()\n",
    "            for i in range(1,len(nums))[::-1]:\n",
    "                diff = a[i]-bar\n",
    "                if diff>0:\n",
    "                    a[i-1]+=diff\n",
    "            return a[0]<=bar\n",
    "\n",
    "        l,r = 0,max(nums)\n",
    "        while l+1<r:\n",
    "            mid = l+(r-l)//2\n",
    "            if check(mid):\n",
    "                r=mid\n",
    "            else:\n",
    "                l=mid\n",
    "        if check(l):\n",
    "            return l\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        def check(limit: int) -> bool:\n",
    "            a = nums.copy()\n",
    "            for i in range(len(a) - 1, 0, -1):\n",
    "                if a[i] > limit:\n",
    "                    a[i - 1] += a[i] - limit \n",
    "            return a[0] <= limit\n",
    "        return bisect_left(range(max(nums)), True, key=check)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "\n",
    "\n",
    "        l = 0\n",
    "        r = sum(nums)\n",
    "        n = len(nums)\n",
    "        def check(x,a):\n",
    "            for i in range(n-1,0,-1):\n",
    "                now = a[i] - x\n",
    "                if now > 0:\n",
    "                   a[i-1] += now\n",
    "            return a[0] <= x\n",
    "        while l < r:\n",
    "            m = l + r >> 1\n",
    "            a = nums.copy()\n",
    "            if check(m,a):\n",
    "                r = m\n",
    "            else:\n",
    "                l = m+1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        # 选择一个大于0的数，nums[i]-1, nums[i-1] + 1\n",
    "\n",
    "        l, r = 0, max(nums)\n",
    "        while l < r:\n",
    "            mid = l + r>> 1\n",
    "            arr = nums[:]\n",
    "            for i in range(len(arr)-1, 0, -1):\n",
    "                if arr[i] > mid:\n",
    "                    arr[i-1] += arr[i] - mid \n",
    "            if arr[0] <= mid: # 如果还能让最大值小一点\n",
    "                r = mid \n",
    "            else:\n",
    "                l = mid + 1\n",
    "\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        l = 0\n",
    "        r = max(nums)\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            arr = list(nums)\n",
    "            if self.check(arr, mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n",
    "\n",
    "        \n",
    "    def check(self, arr, mid):\n",
    "        for i in range(len(arr) - 1, - 1, - 1):\n",
    "            num = arr[i]\n",
    "            if num > mid:\n",
    "                if i == 0:\n",
    "                    return False\n",
    "                arr[i-1] += num - mid\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        # s = sum(nums)\n",
    "        n = len(nums)\n",
    "        pre = list(accumulate(nums))\n",
    "        return max((pre[i]-1)//(i+1) for i in range(n)) +1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        lo, hi = 0, max(nums)+ 1\n",
    "        n = len(nums)\n",
    "        while lo < hi:\n",
    "            mid = (lo + hi ) // 2\n",
    "            # extra = 0\n",
    "            new_arr = [num for num in nums]\n",
    "            for i in range(n-1, 0,-1):\n",
    "                # extra += max(0,    nums[i] + extra-mid)\n",
    "                new_arr[i-1] += max(0, new_arr[i] - mid)\n",
    "\n",
    "            if new_arr[0] > mid:\n",
    "                lo = mid + 1\n",
    "            else:\n",
    "                hi = mid\n",
    "        return lo\n",
    "        # 3 9\n",
    "        # 3+4 5\n",
    "        #   4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        return max((s + i - 1) // i for i, s in enumerate(accumulate(nums), 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def check(self, nums: List[int], k: int) -> bool:\n",
    "        have = 0\n",
    "        for n in nums:\n",
    "            if n <= k:\n",
    "                have += k - n\n",
    "            else:\n",
    "                if have < n - k:\n",
    "                    return False\n",
    "                else:\n",
    "                    have -= (n - k)\n",
    "        return True\n",
    "    \n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        left, right = 0, max(nums)\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if self.check(nums, mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        res = acc = nums[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            acc += nums[i]\n",
    "            res = max(res, acc // (i+1) + int(acc % (i+1) != 0))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        def valid(target):\n",
    "            remaining = 0\n",
    "            for i in range(n - 1, -1, -1):\n",
    "                if nums[i] > target:\n",
    "                    remaining += nums[i] - target # 1WA: should be +=\n",
    "                else:\n",
    "                    remaining = max(0, remaining - (target - nums[i]))\n",
    "            return remaining == 0\n",
    "            \n",
    "        left, right, n = 0, max(nums), len(nums)\n",
    "        while left < right:\n",
    "            mid = left + ((right - left) >> 1)\n",
    "            if valid(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        left, right = min(nums), max(nums)\n",
    "        while left < right:\n",
    "            mid = left + right >> 1\n",
    "            temp = list(nums)\n",
    "            if self.check(temp, mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n",
    "    \n",
    "    def check(self, nums, target):\n",
    "        n = len(nums)\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            if nums[i] >= target:\n",
    "                delta = nums[i] - target\n",
    "                nums[i] = target\n",
    "                nums[i - 1] += delta\n",
    "        return nums[0] <= target\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        def check(x: int) -> bool:\n",
    "            tmp = 0\n",
    "            for i in range(n - 1, 0, -1):\n",
    "                tmp += nums[i] - x\n",
    "                if tmp < 0:\n",
    "                    tmp = 0\n",
    "            return tmp + nums[0] <= x  # 可以使得所有数都不超过x\n",
    "\n",
    "        n = len(nums)\n",
    "        lo, hi = 0, sum(nums)\n",
    "        while lo < hi:\n",
    "            mid = lo + hi >> 1\n",
    "            if not check(mid):\n",
    "                lo = mid + 1\n",
    "            else:\n",
    "                hi = mid\n",
    "        return lo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        return max(ceil(s / i) for i, s in enumerate(accumulate(nums), 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 看到这种“最小化最大值”或者“最大化最小值”可以往二分答案上试试。二分的框架比较容易，这题的主要难度在于check函数怎么写，有点贪心的感觉在里面。思路是这样的：由于对数组的操作宏观上来看其实就是削峰填谷，而0位置的数我们是没法“削”的，所以从后往前遍历检查。假设我现在要将整个数组的最大值压到target，如果遍历到nums[i]>=target，就需要直接削减某个delta使nums[i]降至target（要让数组的最大值不超过target必须这么做，不然现在不管它就没有别的机会管它了），那么它前面的数nums[i-1]就会增加delta。而后面的元素全部都已经“匀”好了，于是再去检查前面的数是不是不超过target。周而复始，最后多余的部分一定被强制加到了nums[0]上，而首元素是没办法再减少的，所以检查一下nums[0]是不是仍然不超过target即可。\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        left, right = min(nums), max(nums)\n",
    "        while left < right:\n",
    "            mid = left + right >> 1\n",
    "            temp = list(nums)\n",
    "            if self.check(temp, mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n",
    "\n",
    "    def check(self, nums, target):\n",
    "        n = len(nums)\n",
    "        for i in range(n-1, 0, -1):\n",
    "            if nums[i] >= target:\n",
    "                delta = nums[i] - target\n",
    "                nums[i] = target\n",
    "                nums[i - 1] += delta\n",
    "        return nums[0] <= target\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        def check(limit: int) -> bool:\n",
    "            a = nums.copy()\n",
    "            for i in range(len(a) - 1, 0, -1):\n",
    "                if a[i] > limit:\n",
    "                    a[i - 1] += a[i] - limit\n",
    "            return a[0] <= limit\n",
    "\n",
    "        # Lower bound\n",
    "        left, right = 0, max(nums)\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #考虑新添一个小于当前均值的数，那么这个数无法去使前面的值更小或是使本身增大，也不会更新答案。\n",
    "    #考虑新添一个大于当前均值的数，那么这个数一定可以将自己的值匀给前面的数，得到最优解。\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        ans,sm=nums[0],nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            sm+=nums[i]\n",
    "            ans=max(ans,ceil(sm/(i+1)))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        pre = list(accumulate(nums))\n",
    "        f = [0]*n \n",
    "        f[0] = nums[0]\n",
    "        for i in range(1,n):\n",
    "            f[i] = f[i-1]\n",
    "            if nums[i]<= f[i-1]:\n",
    "                continue\n",
    "            \n",
    "            f[i] = max(f[i], (pre[i]+i+1-1)//(i+1))\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        l, r = 0, max(nums)\n",
    "        while l < r:\n",
    "            m = (l+r) // 2\n",
    "            flag = True\n",
    "            if m < nums[0]:\n",
    "                flag = False\n",
    "            else:\n",
    "                q = nums.copy()\n",
    "                for i in range(len(nums)-1, 0, -1):\n",
    "                    if m < q[i]:\n",
    "                        q[i-1] += q[i] - m\n",
    "                if q[0] > m:\n",
    "                    flag = False\n",
    "            if flag:\n",
    "                r = m\n",
    "            else:\n",
    "                l = m + 1\n",
    "\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        def check(nums, target):\n",
    "            n = len(nums)\n",
    "            for i in range(n-1, 0, -1):\n",
    "                if nums[i] > target:\n",
    "                    nums[i-1] += nums[i] - target\n",
    "            return nums[0] <= target\n",
    "\n",
    "        left, right = min(nums), max(nums)\n",
    "        while left < right:\n",
    "            mid = (left + right)//2\n",
    "            temp = list(nums)\n",
    "            if check(temp, mid): # nums[0] <= target 说明，最大值还可以更小\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "       \n",
    "        return left\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        presum = [nums[0]]\n",
    "        for i in nums[1:]:\n",
    "            presum.append(presum[-1]+i)\n",
    "        ret = 0\n",
    "        for i in range(len(presum)):\n",
    "            d, m = divmod(presum[i], i+1)\n",
    "            if m > 0:\n",
    "                d += 1\n",
    "            if d > ret:\n",
    "                ret = d\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "\n",
    "\n",
    "        n = len(nums)\n",
    "        def check(x):\n",
    "            diff = 0\n",
    "            for i in range(n - 1, 0, -1):\n",
    "                if nums[i] + diff > x:\n",
    "                    diff = nums[i] + diff - x\n",
    "                else:\n",
    "                    diff = 0\n",
    "            return nums[0] + diff <= x\n",
    "        ans = -inf\n",
    "        l, r = 0, 10 ** 10\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        def check(limit: int) -> bool:\n",
    "            extra = 0\n",
    "            for i in range(len(nums) - 1, 0, -1):\n",
    "                extra = max(nums[i] + extra - limit, 0)\n",
    "            return nums[0] + extra <= limit\n",
    "        return bisect_left(range(max(nums)), True, key=check)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\r\n",
    "        # 二分查找\r\n",
    "        # 找到能够使nums均小于k的结果，找到这个k\r\n",
    "        # k=mid的值用二分查找，最小值为min(nums)，最大值为max(nums)\r\n",
    "        left, right = min(nums), max(nums)\r\n",
    "        while left < right:\r\n",
    "            mid = left + (right - left) // 2\r\n",
    "            # 当nums调整后最大元素为mid时，探究还能不能更小，因为要min（最大值）\r\n",
    "            if self.check(nums, mid):\r\n",
    "                right = mid\r\n",
    "            # nums调整后，最大元素超过mid，说明没有找到使所有元素小于mid的这个mid值，因此调整二分的左端点使得mid取大一点看能否满足\r\n",
    "            else:\r\n",
    "                left = mid + 1\r\n",
    "        return left\r\n",
    "\r\n",
    "\r\n",
    "    \r\n",
    "    def check(self, nums: list[int], k:int) -> bool:\r\n",
    "        # nums经过调整后最大值为k是否能够做到\r\n",
    "        # have记录前一个元素需要多少\r\n",
    "        have = 0\r\n",
    "        for num in nums:\r\n",
    "            if num <= k:\r\n",
    "                # 记录元素还差多少达到k\r\n",
    "                have += k - num\r\n",
    "            else:\r\n",
    "                # 超过k的要补给前面的\r\n",
    "                # 当不够补给时\r\n",
    "                if have < num - k:\r\n",
    "                    return False\r\n",
    "                else:\r\n",
    "                    have -= num - k\r\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        ls=copy.deepcopy(nums)\n",
    "        def check(x):\n",
    "            #print(x)\n",
    "            nums=copy.deepcopy(ls)\n",
    "            if x<nums[0]:\n",
    "                #print(\"f1\")\n",
    "                return False\n",
    "            for i in range(n-1):\n",
    "                #if nums[i]<0:\n",
    "                #    nums[i]=0\n",
    "                #if x<15:\n",
    "                    #print(i,nums[i])\n",
    "                if nums[i]<=x:\n",
    "                    k=x-nums[i]\n",
    "                    nums[i+1]-=k\n",
    "                else:\n",
    "                    #print(\"f2\")\n",
    "                    return False\n",
    "            if nums[-1]>x:\n",
    "                return False\n",
    "            #print(\"t\")\n",
    "            return True\n",
    "        ret=bisect_left(range(10**9+5),True,key=check)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\r\n",
    "        left, right = min(nums), max(nums)\r\n",
    "        while left < right:\r\n",
    "            mid = left + (right - left) // 2\r\n",
    "            if self.check(nums, mid):\r\n",
    "                right = mid\r\n",
    "            else:\r\n",
    "                left = mid + 1\r\n",
    "        return left\r\n",
    "\r\n",
    "\r\n",
    "    \r\n",
    "    def check(self, nums: list[int], k:int) -> bool:\r\n",
    "        # nums经过调整后最大值为k是否能够做到\r\n",
    "        # have记录前一个元素需要多少\r\n",
    "        have = 0\r\n",
    "        for num in nums:\r\n",
    "            if num <= k:\r\n",
    "                # 记录元素还差多少达到k\r\n",
    "                have += k - num\r\n",
    "            else:\r\n",
    "                # 超过k的要补给前面的\r\n",
    "                # 当不够补给时\r\n",
    "                if have < num - k:\r\n",
    "                    return False\r\n",
    "                else:\r\n",
    "                    have -= num - k\r\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        mx=nums[0]\n",
    "        n=len(nums)\n",
    "        deposit=0\n",
    "        for i in range(1,n):\n",
    "            if nums[i]>mx:\n",
    "                if (nums[i]-mx)<=deposit:\n",
    "                    deposit=deposit- (nums[i]-mx)\n",
    "                else:\n",
    "                    tmp=(nums[i]-mx)-deposit\n",
    "                    if tmp%(i+1)==0:\n",
    "                        mx=mx+tmp//(i+1)\n",
    "                        deposit=0\n",
    "                    else:\n",
    "                        c=tmp//(i+1)+1\n",
    "                        mx=mx+c\n",
    "                        deposit=c*(i+1)-tmp\n",
    "            elif nums[i]<mx:\n",
    "                deposit+=mx-nums[i]\n",
    "        return mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #考虑新添一个小于当前均值的数，那么这个数无法去使前面的值更小或是使本身增大，也不会更新答案。\n",
    "    #考虑新添一个大于当前均值的数，那么这个数一定可以将自己的值匀给前面的数，得到最优解。\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        ans,sm=nums[0],nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            sm+=nums[i]\n",
    "            ans=max(ans,ceil(sm/(i+1)))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        cur = 0\n",
    "        for i, num in enumerate(nums,1):\n",
    "            cur += num\n",
    "            ans = max(ans, (cur+i-1)//i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "        res = 0\n",
    "        sum1 = 0\n",
    "        for i in range(len(nums)):\n",
    "            sum1+=nums[i]\n",
    "            res =max(res,ceil(sum1/(i+1))) \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        return max((s + i - 1) // i for i, s in enumerate(accumulate(nums), 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        def check(k:int) -> bool:\n",
    "            have = 0\n",
    "            for v in nums:\n",
    "                if v <= k:\n",
    "                    have+= k - v \n",
    "                else:\n",
    "                    if have < v - k :\n",
    "                        return False \n",
    "                    else:\n",
    "                        have -= v-k\n",
    "\n",
    "            return True \n",
    "        return bisect_left(range(max(nums)),True,key=check)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        def check(k):\n",
    "            have=0\n",
    "            for n in nums:\n",
    "                if n<=k:\n",
    "                    have+=k-n\n",
    "                else:\n",
    "                    if have<n-k:\n",
    "                        return False\n",
    "                    have-=n-k\n",
    "            return True\n",
    "        l,r=0,max(nums)\n",
    "        while l<r:\n",
    "            mid=l+(r-l)//2\n",
    "            if check(mid):\n",
    "                r=mid\n",
    "            else:\n",
    "                l=mid+1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeArrayValue(self, nums: List[int]) -> int:\n",
    "        # 可以得到limit，返回True\n",
    "        def check(limit):\n",
    "            a = nums.copy()\n",
    "            for i in range(len(a)-1, 0, -1):\n",
    "                if a[i] > limit:\n",
    "                    a[i-1] += a[i] - limit\n",
    "            return a[0] <= limit\n",
    "\n",
    "\n",
    "        return bisect.bisect_right(range(0, max(nums)+1), False, key = check)\n",
    "\n",
    "        # left, right = 0, max(nums)+1\n",
    "        # while left < right:\n",
    "        #     mid = (left + right) // 2\n",
    "        #     # 可以得到limit，尝试right右移\n",
    "        #     if check(mid):\n",
    "        #         right = mid\n",
    "        #     else:\n",
    "        #         left = mid + 1\n",
    "        # return left"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
